The present invention relates to a method and apparatus for coding and decoding an image. More particularly the present invention relates to a method and apparatus of coding and decoding an image by the use of a motion compensation method wherein an image is divided, into patches and each patch is deformed by affine or bilinear transformation.
In the case of high-efficiency coding of a dynamic image by a coder, it is known that motion compensation is very effective for data compression due to similarity between frames temporally close to each other. The processing of an image by motion compensation is performed according to equation 1, shown below. In this case, it is assumed that the predicted image of a frame (current frame) to be coded is P(x,y) and a reference image (decoded image of a frame which is temporally close to P and whose coding is already completed) is R(x,y). Moreover, it is assumed that x and y are integers and a pixel is present at a point whose coordinate values are integers for P and R. In this case, the relation between P and R is also shown by the equation 1 shown below.
P(x,y)=R(fi(x,y),gi(x,y)),(x,y)xcex5Pi,0xe2x89xa6i less than N xe2x80x83xe2x80x83Equation 1 
In this case, Pi denotes a pixel included in the i-th patch of an image by assuming that the image is divided into N small regions (patches). Moreover, transformation functions fi(x,y) and gi(x,y) show the spatial correspondence between the image of a current frame and a reference image. In this case, the motion vector of the pixel (x,y) in Pi can be shown by (fi(x,y)xe2x88x92x, gi(x,y)xe2x88x92y) by using the coordinates of a pixel in a predicted image as a starting point and the coordinates of a correspondent point in the reference image as an ending point.
In the case of H.261, of Motion Picture Experts Group (MPEG)1, and MPEG2 which are the international standards for the video coding method, a method referred to as block matching is used in which fi(x,y)xe2x88x92x and gi(x,y)xe2x88x92y are constants unrelated to x or y. However, to achieve a data compression ratio higher than these standard coding methods, it is required to use a higher-level motion compensation method. As the above new motion compensation method, a motion compensation method has recently been proposed which allows that fi(x,y)xe2x88x92x and gi(x,y)xe2x88x92y are not constants but pixels in the same patch have different motion vectors. As transformation functions of these methods, the following examples have been disclosed.
xe2x80x9cBasic study of motion compensation according to triangle patchxe2x80x9d, by Nakaya et al., Technical report of IEICE, IE90-106, Hei 2-03 discloses an example of affine transform as follows:
fi(x,y)=ai0x+ai1y+ai2 
gi(x,y)=ai3x+ai4y+ai5 xe2x80x83xe2x80x83Equation 2 
xe2x80x9cMotion compensation for video compression control grid interpolationxe2x80x9d, by G. J. Sullivan et al., Proc. ICASSP ""91, M9.1, pp. 2713-2716, 1991-05 discloses an example of bilinear transform as follows:
fi(x,y)=bi0xy+bi1x+bi2y+bi3 
gi(x,y)=bi4xy+bi5x+bi6y+bi7 xe2x80x83xe2x80x83Equation 3 
In the above equations, aij and bij denote motion parameters estimated for each patch. When the value of a transformation function is not an integer, coordinate values are not integers. Therefore, it is necessary to obtain the luminance value of a point where no pixel is actually present in a reference image. In this case, bilinear interpolation using four peripheral pixels is frequently performed. When describing the above interpolation method in the form of the equation, R(x+"xgr",y+xcex7) is shown below by assuming 0xe2x89xa6"xgr", xcex7 less than 1.
R(x+"xgr",y+xcex7)=(1xe2x88x92xcex7)((1xe2x88x92"xgr")R(x,y)+"xgr"R(x+1, y))+xcex7(1xe2x88x92"xgr")R(x,y+1)+"xgr"R(x+1,y+1)) xe2x80x83xe2x80x83Equation 4 
Hereinafter, the motion compensation method using the transformation functions in the above equations 2 and 3 is referred to as warping prediction.
To transmit motion information, a video coder must transmit information capable of specifying the motion parameter of a transformation function to the receiving side in some manner. For example, the transformation function uses affine transform and the shape of a patch is assumed as a triangle. In this case, even if six motion parameters are directly transmitted to or the motion vectors of three apexes of the patch are transmitted to the receiving side, it must be possible for the receiving side to reproduce the six motion parameters ai1 to ai6.
FIGS. 1a-d illustrate an example of the motion compensation method of transmitting motion vectors of apexes (grid points) of a triangle patch. FIGS. 1a-d illustrate the processing for synthesizing a predicted image of an original image 102 of a current frame by using a reference image 101. First, the current frame is divided into a plurality of polygonal patches and formed into a patch-divided image 108 as illustrated in FIG. 1d. An apex of a patch is referred to as a grid point and each grid point is shared by a plurality of patches. For example, a patch 109 is formed with grid points 110, 111, and 112 and these grid points also serve as apexes of another patch. Thus, after an image is divided into a plurality of patches, motion estimation is performed.
In the case of the example shown in FIGS. 1a-b, motion estimation is performed between the predicted image and the reference image for each grid point. As a result, each patch is deformed by a reference image 103 after motion estimation as illustrated in FIG. 1c. For example, the patch 109 corresponds to a deformed patch 104. This is because it is estimated that grid points 105, 106, and 107 respectively correspond to the grid points 110, 111, and 112. In the case of this example, when assuming the coordinates of the grid points 110, 111, and 112 as (I,J), (I+r,J), and (I,J+s) (where I, J, r, and s are integers) respectively and the motion vectors of the points as (U1,V1), (U2,V2), and (U3,V3) respectively, the motion vector (ua(x,y),va(x,y)) at the point (x,y) in the patch can be shown by the following equation 5 in accordance with the relation of the equation 2.                                                                                           u                  a                                ⁡                                  (                                      x                    ,                    y                                    )                                            =                              xe2x80x83                            ⁢                                                                                                                  U                        1                                            -                                              U                        0                                                              r                                    ⁢                                      (                                          x                      -                      I                                        )                                                  +                                                                                                    U                        2                                            -                                              U                        0                                                              s                                    ⁢                                      (                                          y                      -                      J                                        )                                                  +                                  U                  0                                                                                                                                          v                  a                                ⁡                                  (                                      x                    ,                    y                                    )                                            =                              xe2x80x83                            ⁢                                                                                                                  V                        1                                            -                                              V                        0                                                              r                                    ⁢                                      (                                          x                      -                      I                                        )                                                  +                                                                                                    V                        2                                            -                                              V                        0                                                              s                                    ⁢                                      (                                          y                      -                      J                                        )                                                  +                                  V                  0                                                                                        Equation  5            
By using the relation, it is possible to obtain the motion vector for each pixel and synthesize a predicted image.
Moreover, when deforming a quadrangular patch by using bilinear transform, the motion vector ub(x,y),vb(x,y) at a point (x,y) in the patch can be shown by the following equation in accordance with the relation of the equation 3 by assuming the coordinates of grid points as (I,J), (I+r,J), (I,J+s), and (I+r,J+s) and the motion vectors of the points as (U1,V1), (U2,V2), (U3,V3), and (U4,V4).                                                                         ub                ⁡                                  (                                      x                    ,                    y                                    )                                            =                              xe2x80x83                            ⁢                                                                                          J                      +                      s                      -                      y                                        s                                    ⁢                                      (                                                                                                                        I                            +                            r                            -                            x                                                    r                                                ⁢                                                  U                          0                                                                    +                                                                                                    x                            -                            I                                                    r                                                ⁢                                                  U                          1                                                                                      )                                                  +                                                                            y                      -                      J                                        s                                    ⁢                                      (                                                                                                                        I                            +                            r                            -                            x                                                    r                                                ⁢                                                  U                          2                                                                    +                                                                                                    x                            -                            I                                                    r                                                ⁢                                                  U                          3                                                                                      )                                                                                                                          =                              xe2x80x83                            ⁢                                                                                                                  U                        0                                            -                                              U                        1                                            -                                              U                        2                                            +                                              U                        3                                                              rs                                    ⁢                                      (                                          x                      -                      I                                        )                                    ⁢                                      (                                          y                      -                      J                                        )                                                  +                                                                                                    -                                                  U                          0                                                                    +                                              U                        1                                                              r                                    ⁢                                      (                                          x                      -                      I                                        )                                                                                                                                                            +                                      xe2x80x83                                    ⁢                                                                                    -                                                  U                          0                                                                    +                                              U                        2                                                              s                                                  ⁢                                  (                                      y                    -                    J                                    )                                            +                              U                0                                                                                                        vb                ⁡                                  (                                      x                    ,                    y                                    )                                            =                              xe2x80x83                            ⁢                                                                                                                  V                        0                                            -                                              V                        1                                            -                                              V                        2                                            +                                              V                        3                                                              rs                                    ⁢                                      (                                          x                      -                      I                                        )                                    ⁢                                      (                                          y                      -                      J                                        )                                                  +                                                                                                    -                                                  V                          0                                                                    +                                              V                        1                                                              r                                    ⁢                                      (                                          x                      -                      I                                        )                                                                                                                                                            +                                      xe2x80x83                                    ⁢                                                                                    -                                                  V                          0                                                                    +                                              V                        2                                                              s                                                  ⁢                                  (                                      y                    -                    J                                    )                                            +                              V                0                                                                        Equation  6            
By introducing the above-described warping prediction, it is possible to accurately approximate the motion vectors of an image sequence and realize a high data compression ratio. However, the throughput for coding and decoding decreases compared to a conventional method. Particularly, the divisions performed in the equations 5 and 6 are large factors for complicating the processing. Therefore, the warping prediction using affine transform and bilinear transform has a problem that the throughput for synthesizing a predicted image decreases.
It is an object of the present invention to decrease the number of operations performed in an image coding process by replacing the division processing in the warping prediction with a binary shift operation.
The division processing can be realized by a shift operation by obtaining and using the motion vector of an assumed grid point (representative point).
The present invention provides a method, apparatus and computer program for synthesizing an inter-frame predicted image using a motion compensation process of dividing an image into N patches, wherein N is a positive integer, and deforming the patches through affine transform. Pixel sampling of an image is performed at an interval of 1 in the horizontal and vertical directions and a sampling point is present on a point in which the horizontal and vertical components of coordinates are integers.
The inter-frame predicted image is synthesized by obtaining motion vectors of three representative points in which coordinates are represented by (Ixe2x80x2, Jxe2x80x2), (Ixe2x80x2+p, Jxe2x80x2), and (Ixe2x80x2, Jxe2x80x2+q) in at least in one patch Pa, and computing a motion vector of each pixel in the patch using the motion vectors of the three representative points. Either of p and xe2x88x92p is equal to 2xcex1, where xcex1 is a positive integer, in the patch Pa, and either of q and xe2x88x92q is equal to 2xcex2, where xcex2 is a positive integer, in the patch Pa. A triangle formed by said three representative points in the patch Pa does not coincide with the shape of the patch.
The present invention also provides a method apparatus and computer program for synthesizing an inter-frame predicted image using a motion compensation process of dividing an image into N patches, wherein N is a positive integer, and deforming the patches through bilinear transform. Pixel sampling of an image is performed at an interval of 1 in the horizontal and vertical directions and a sampling point is present on a point in which the horizontal and vertical components of coordinates are integers.
The inter-frame predicted image is synthesized by obtaining motion vectors of four representative points in which coordinates are represented by (Ixe2x80x2,Jxe2x80x2), (Ixe2x80x2+p,Jxe2x80x2), (Ixe2x80x2,Jxe2x80x2+q), and (Ixe2x80x2+p,Jxe2x80x2+q) in at least one patch Pb and computing a motion vector of each pixel in the at least one patch using the motion vectors of the four representative points. Either of p and xe2x88x92p is equal to 2xcex1, where xcex1 is a positive integer, in the at least one patch Pb and either of q and xe2x88x92q is equal to 2xcex2, where xcex2 is a positive integer, in the at least one patch Pb. A rectangle formed by the four representative points in the at least one patch Pb does not coincide with the shape of the patch.